import java.util.ArrayList;
import java.util.Arrays;

public class BitManipulations {
    /*
        5.1 You are given two 32-bit numbers, N and M, and two bit positions, land j. Write a method to insert M
        into N such that M starts at bit j and ends at bit i. You can assume that the bits j through i have enough space
        to fit all of M. That is, if M = 10011, you can assume that there are at least 5 bits between j and i.
        You would not, for example, have j = 3 and i = 2, because M could not fully fit between bit 3 and bit 2.
        EXAMPLE  Input: N = 10000000000, M = 10011, i = 2, j = 6     Output: N = 10001001100
     */
    public static int insertTheInt(int N, int M, int i, int j) {
        int ones = ~0;
        int leftMask = ones << (j - 1);
        int rightMask = (1 << i) - 1;
        int mask = leftMask | rightMask;
        int cleared = N & mask;
        int shifted = M << i;
        return cleared | shifted;
    }

    public static void main(String[] args) {
        int N = Integer.parseInt("10000000000", 2);
        int M = Integer.parseInt("10011", 2);
        int i = 2, j = 6;
        System.out.println(Integer.toBinaryString(insertTheInt(N, M, i, j)));
        double number = 0.25;
        System.out.println("What about a binary representation for a double " + number + "? Here it is: " + getBinaryString(number));
        int intNumber = Integer.parseInt("1101100", 2);
        System.out.println("The next number for " + Integer.toBinaryString(intNumber) + "  is " + Integer.toBinaryString(getNextInt(intNumber)));
        System.out.println("The previous number for " + Integer.toBinaryString(intNumber) + "  is " + Integer.toBinaryString(getPrevInt(intNumber)));
        System.out.println();
        System.out.println("The number of different bits in "
                + Integer.toBinaryString(N) + " and " + Integer.toBinaryString(M) + " is: " + getNumberOfDifBits(N, M));
        System.out.println();
        System.out.println("Let's swap the bits in " + Integer.toBinaryString(M) + ": " + Integer.toBinaryString(swapOddEvenBits(M)));
        System.out.println("Find missing number: " + findMissing(new ArrayList<Integer>(Arrays.asList(new Integer[]{1, 3, 4, 2, 6,0}))));
    }

    /*
        5.3 Given a positive integer, print the next smallest and the next largest number that
        have the same number of 1 bits in their binary representation.
     */
    public static int getNextInt(int intNumber) {
        int c0 = 0, c1 = 0;
        int c = intNumber;
        while (((c & 1) == 0) && c != 0) {
            c0++;
            c >>= 1;
        }
        while ((c & 1) == 1) {
            c1++;
            c >>= 1;
        }
        int p = c0 + c1;
        if (p == 31 || p == 0) return -1;

        intNumber |= 1 << p; // Set the p-th (zero) bit to 1;
        intNumber &= (~0) << p; //Set the last p-1 bits to 0;
        intNumber |= (1 << (c1 - 1)) - 1; // Set right c1-1 bits to 1;
        return intNumber;
    }

    public static int getPrevInt(int intNumber) {
        int c0 = 0, c1 = 0;
        int c = intNumber;
        while ((c & 1) == 1) {
            c1++;
            c >>= 1;
        }
        if (c == 0) return -1;

        while ((c & 1) == 0 && c != 0) {
            c0++;
            c >>= 1;
        }

        int p = c0 + c1;
        intNumber &= (~0) << (p + 1); // last positions [p..0] are set to 0
        intNumber |= (((1 << (c1 + 1)) - 1) << (c0 - 1));

        return intNumber;

    }

    /*
        5.2 Given a real number between 0 and 7 (e.g., 0.72) that is passed in as a double, print the binary representation.
        If the number cannot be represented accurately in binary with at most 32 characters, print "ERROR."
     */
    public static String getBinaryString(double number) {
        if (number >= 1 || number <= 0) return "ERROR";
        StringBuilder result = new StringBuilder("0.");
        for (int i = 0; i < 32; i++) {
            double n = 2 * number;
            if (n >= 1) {
                result.append("1");
                number = n - 1;
            } else {
                result.append("0");
                number = n;
            }
            if (number <= 0) return result.toString();
        }
        return "ERROR";
    }
    /*
        5.4 Explain what the following code does: ((n & (n-1)) == 0).  ===>  It's a power-of-two check for n
    */

    /*
        5.5 Write a function to determine the number of bits required to convert integer A to integer B.
    */
    public static int getNumberOfDifBits(int A, int B) {
        int counter = 0;
        for (int xor = A ^ B; xor > 0; xor = xor & (xor - 1)) counter++;
        return counter;
    }

    /*
        5.6 Write a program to swap odd and even bits in an integer with as few instructions as
            possible (e.g., bit 0 and bit! are swapped, bit 2 and bit 3 are swapped, and so on).
     */
    public static int swapOddEvenBits(int number) {
        return (((number & 0xaaaaaaaa) >> 1) | ((number & 0x55555555) << 1));
    }

    /*
        5.7 An array A contains all the integers from 0 to n, except for one number which is missing. In this problem,
        we cannot access an entire integer in A with a single operation. The elements of A are represented in binary,
        and the only operation we can use to access them is "fetch the jth bit of A[i]," which takes constant time.
        Write code to find the missing integer. Can you do it in 0(n) time?
    */
     public static int findMissing(ArrayList<Integer> array) {
        int n = array.size();
        int bitsLength = (int) (Math.log(n) / Math.log(2)) + 1;
        return findMissing(array, bitsLength - 1);
    }

    private static int findMissing(ArrayList<Integer> input, int column) {
        if (column < 0) { // Base case and error condition
            return 0;
        }
        ArrayList<Integer> oneBits = new ArrayList<Integer>(input.size() / 2);
        ArrayList<Integer> zeroBits = new ArrayList<Integer>(input.size() / 2);
        for (Integer t : input) {
            if (!fetchBitAt(t, column)) {
                zeroBits.add(t);
            } else {
                oneBits.add(t);
            }
        }
        if (zeroBits.size() <= oneBits.size()) {
            int v = findMissing(zeroBits, column - 1);
            System.out.print("0");
            return (v << 1) | 0;
        } else {
            int v = findMissing(oneBits, column - 1);
            System.out.print("1");
            return (v << 1) | 1;
        }
    }

    public static boolean fetchBitAt(Integer number, int index) {
        return (number & (1 << index)) != 0;
    }
    /*
        5.8 A monochrome screen is stored as a single array of bytes, allowing eight consecutive pixels to be stored in one byte.
        The screen has width w, where w is divisible by 8 (that is, no byte will be split across rows).
        The height of the screen, of course, can be derived from the length of the array and the width.
        Implement a function drawHorizontall_ine(byte[] screen, int width, int xl, int x2, int y) which draws a horizontal line from (xl, y)to(x2, y).
   */

}
